package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1054 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[] rearrangeBarcodes(int[] barcodes) {
            Map<Integer, Integer> dict = new HashMap<>();
            for (int barcode : barcodes) {
                dict.put(barcode, dict.getOrDefault(barcode, 0) + 1);
            }

            TreeMap<Integer, List<Integer>> cntMap = new TreeMap<>(Collections.reverseOrder());
            for (Integer num : dict.keySet()) {
                int cnt = dict.get(num);
                if (cntMap.containsKey(cnt)) cntMap.get(cnt).add(num);
                else {
                    List<Integer> list = new ArrayList<>();
                    list.add(num);
                    cntMap.put(cnt, list);
                }
            }

            int[] res = new int[barcodes.length];
            int curInsertPos = 0;

            for (Integer cnt : cntMap.keySet()) {
                final List<Integer> list = cntMap.get(cnt);
                for (Integer num : list) {
                    for (int i = 0; i < cnt; i++) {
                        res[curInsertPos] = num;
                        curInsertPos += 2;
                        if (curInsertPos >= res.length) curInsertPos = 1;
                    }
                }
            }

            return res;

            // 后面的解法比较蠢慢
//            Map<Integer, Integer> dict = new HashMap<>();
//            for (int barcode : barcodes) {
//                dict.put(barcode, dict.getOrDefault(barcode, 0) + 1);
//            }
//
//            TreeMap<Integer, List<Integer>> cntMap = new TreeMap<>(Collections.reverseOrder());
//            for (Integer num : dict.keySet()) {
//                int cnt = dict.get(num);
//                if (cntMap.containsKey(cnt)) cntMap.get(cnt).add(num);
//                else {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(num);
//                    cntMap.put(cnt, list);
//                }
//            }
//
//            List<Integer> res = new ArrayList<>();
//
//            for (Integer cnt : cntMap.keySet()) {
//                for (int i = 0; i < cnt; i++) {
//                    res.addAll(cntMap.get(cnt));
//                }
//            }
//
//            int[] outRes = new int[barcodes.length];
//            int i = 0;
//            for (Integer re : res) {
//                outRes[i++] = re;
//            }
//            return outRes;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,1,1,2,2,2]");
        System.out.println(Arrays.toString(solution.rearrangeBarcodes(arr)));
    }

    public static void main(String[] args) throws Exception {
        LC1054 an = new LC1054();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
